package oj;

public class LC121 {
    public int maxProfit (int[] prices) {
        // 动态规划
        int[][] dp=new int[prices.length][2];
        dp[0][0]=0;
        dp[0][1]=-prices[0];
        for(int i=1;i<prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);

        }
        return dp[prices.length-1][0];

        //一次遍历
//        int min=Integer.MAX_VALUE;
//        int ans=0;
//        for(int i=0;i<prices.length;i++){
//            if(prices[i]<min){
//                min=prices[i];
//            }else if( prices[i]-min>ans){
//                ans=prices[i]-min;
//            }
//        }
//        return ans;
    }
}
